package Demo;

public class MySingleList implements IList {
    private ListNode head;

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
            this.next = null;
        }
    }
    public ListNode cur; // 临时头节点

    public void createList(){
        ListNode node1 = new ListNode(12);
        ListNode node2 = new ListNode(23);
        ListNode node3 = new ListNode(34);
        ListNode node4 = new ListNode(45);
        ListNode node5 = new ListNode(56);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        this.cur = node1;
    }

    @Override
    public void addFirst(int data) {
//        头插法
        ListNode newNode = new ListNode(data);
        newNode.next = head;
        head = newNode;
    }

    @Override
    public void addLast(int data) {
        ListNode newNode = new ListNode(data);
        ListNode cur = this.head;
        if (cur == null){
//            检查空链表
            head = newNode;
            return;
        }
            //        先遍历链表 找到最后一个
            while(cur.next != null){
                cur = cur.next;
            }
//        找到最后一个节点  尾插数据
            cur.next = newNode;
    }

    @Override
    public void addIndex(int index, int data) {
        //任意位置插入,第一个数据节点为0号下标
        ListNode cur = this.head;
        if (index < 0 || index > size()){
            System.out.println("非法位置");
            return;
        } else if (index == 0) {
            addFirst(data);
            return;
        } else if (index == size()) {
            addLast(data);
            return;
        }else {
            for (int i = 0; i < index-1; i++) {
                cur = cur.next;
            }
            ListNode node = new ListNode(data);
            node.next = cur.next;
            cur.next = node;
        }
    }

    @Override
    public int size() {
        int count = 0;
        ListNode cur = this.head;
        while(cur != null){
            cur = cur.next;
            count++;
        }
        return count;
    }
    @Override
    public boolean contains(int key) {
        ListNode cur = this.head;
        while(cur != null){
            if (cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
//删除第一次出现关键字为key的节点

//        处理头节点是key
        if (head != null && head.val == key){
         head = head.next;
         return;
        }
        ListNode cur = head;
        while(cur != null && cur.next != null){
//            cur.next != null  防止空指针异常
            if (cur.next.val == key){
                cur.next = cur.next.next;
                return;
            }else {
                cur = cur.next;
            }
        }
    }

    @Override
    public void removeAllKey(int key) {
//        删除所有关键字为key的节点
        // 处理头节点是 key 的情况
        while (head != null && head.val == key) {
            head = head.next; // 重复删除头节点直到头节点不是 key
        }

        ListNode cur = head;
        while (cur != null && cur.next != null) {
            if (cur.next.val == key) {
                cur.next = cur.next.next; // 删除所有匹配的节点
            } else {
                cur = cur.next; // 继续向后移动
            }
        }
    }

    @Override
    public void clear() {
        this.head = null;
    }

    @Override
    public void display() {
        ListNode cur = this.head;
        while(cur != null){
//            遍历链表 如果为 null说明遍历完成
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
    }

//    反转链表
    public ListNode reverseList() {
        // 定义两个指针，pre初始化为null，用于存储反转后的链表
        ListNode pre = null;
        // cur初始化为head，表示当前处理的节点
        ListNode cur = head;

        // 循环直到cur为null，表示已经处理完所有节点
        while(cur != null){
            // temp临时存储cur的下一个节点，因为接下来要修改cur.next
            ListNode temp = cur.next;

            // 将cur的next指针指向pre，实现反转
            cur.next = pre;

            // pre和cur都前进一步
            pre = cur; // pre移动到cur的位置
            cur = temp; // cur移动到下一个待处理的节点
        }

        // 当cur为null时，pre就是新链表的头节点
        return pre;
    }

//    链表的中心节点
    public ListNode middleNode() {
        // 定义快慢指针，都初始化为头节点head
        ListNode fast = head;
        ListNode slow = head;

        // 循环条件，快指针fast及其next不为null
        while (fast != null && fast.next != null) {
            // 快指针fast每次向前移动两步
            fast = fast.next.next;
            // 慢指针slow每次向前移动一步
            slow = slow.next;
        }

        // 当快指针到达链表末尾时，慢指针正好到达中间节点
        return slow;
    }

//    链表中倒数 K 个节点
    public ListNode FindKthToTail(ListNode pHead, int k) {
        // 初始化快慢指针，均指向链表头节点
        ListNode fast = pHead;
        ListNode slow = pHead;
        if(k <= 0 || pHead == null){
            return null;
        }

        // 让快指针先向前移动k-1步
        for (int i = 0; i < k-1; i++) {
            fast = fast.next;
            // 如果在移动过程中快指针遇到null，说明链表长度小于k
            if (fast == null) {
                return null;  // 因链表长度不足，返回null
            }
        }

        // 快指针继续向前移动直到链表末尾
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 当快指针到达链表末尾时，慢指针即位于倒数第k个节点
        return slow;
    }

//    合并两个有序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);//虚拟节点

        // 创建一个指针cur，用来遍历并构建新的合并后的链表，初始指向虚拟节点
        ListNode cur = dummy;

        // 遍历链表直到其中一个为空
        while(list1 != null && list2 != null){
            if(list1.val > list2.val){
                cur.next = list2;
                list2 = list2.next;
            }else{
                cur.next = list1;
                list1 = list1.next;
            }
            cur = cur.next;
        }

        // 如果其中一个链表先遍历完，将另一个链表的剩余部分连接到新链表的末尾
        cur.next = (list1 == null) ? list2:list1;
        return dummy.next; //返回虚拟节点的下一个节点
    }

//    删除链表的倒数第 N 个节点
    public ListNode removeNthFromEnd(int n) {
        // 思路 : 用双指针先找到第n个节点 然后再进行删除操作

        // 创建一个虚拟节点，用于简化边界条件的处理
        ListNode dummy = new ListNode(-1);
        // 将虚拟节点的next指针指向链表的头节点
        dummy.next = head;

        // 初始化快慢双指针，起始位置均指向虚拟节点
        ListNode fast = dummy;
        ListNode slow = dummy;

        // 让fast指针先向前移动n+1步，以便在后续循环中保持与slow指针之间的距离为n
        for (int i = 0; i < n + 1; i++) {
            fast = fast.next;
        }

        // 同时移动fast和slow指针，直到fast指针到达链表的末尾
        // 此时slow指针正好位于要删除节点的前一个节点
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 删除该节点，即将slow指针的next指向其下一个节点的next，跳过要删除的节点
        slow.next = slow.next.next;

        // 返回新链表的头节点，即虚拟节点的next
        return dummy.next;
    }

//    链表分割
    public ListNode partition(ListNode pHead, int x) {
        // 定义两个虚拟头节点 区分 小于x, 大于等于x的节点
        ListNode smalldummy = new ListNode(-1);
        ListNode bigdummy = new ListNode(-1);

        // 定义两个指针 分别指向对应的虚拟节点
        ListNode p1 = smalldummy;
        ListNode p2 = bigdummy;

        // 遍历 将节点分配到两个链表当中
        ListNode cur = pHead;
        while(cur != null){
            if(cur.val < x){
                p1.next = cur;
                p1 = p1.next;
            }else{
                p2.next = cur;
                p2 = p2.next;
            }
            cur = cur.next;
        }

        // 遍历结束  开始合并
        p2.next = null;
        p1.next = bigdummy.next;
        return smalldummy.next;
    }

//    判断是否为环形链表
    public boolean hasCycle() {
        // 使用快慢指针 如果两个指针相遇 说明有环

        if(head == null){
            return false;
        }

        // 定义快慢指针
        ListNode fast = head;
        ListNode slow = head;

        while(fast.next != null && fast.next.next != null){
            // 确保快指针不会空指针异常
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }

//    链表的回文结构
    public boolean chkPalindrome(ListNode A) {
        //    用快慢指针 先用慢指针找到链表的中心节点
        // 反转链表的后半部分 看前后部分是否相同

        if (A == null || A.next == null) return true;
        ListNode fast = A;
        ListNode slow = A;
        while(fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        // 此时已经找到中间节点 开始翻转后半部分的链表
        ListNode cur = slow.next;
        ListNode pre = null;
        while(cur != null){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }

        // 翻转完成 开始比对前后部分
        ListNode p1 = A;
        ListNode p2 = pre;
        while(p2 != null){
            if(p1.val != p2.val){
                return false;
            }
            p1 = p1.next;
            p2= p2.next;
        }
        return true;
    }

//        相交链表
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 思路: 先求出两个链表长度 让长链表先走 K步(两个链表相差的距离)
        //      然后再一起走  直到走到交点

        int sizeA = size(headA);
        int sizeB = size(headB);


        // 多走k步
        if(sizeA > sizeB){
            headA = move(headA,(sizeA - sizeB));
        }else{
            headB = move(headB,(sizeB-sizeA));
        }

        // 同时遍历两个链表 直到找到交点
        while(headA != null && headB != null){
            if(headA == headB){
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }
    // 方法: 让长的链表多走 K步
    private ListNode move(ListNode head, int k){
        while(k > 0){
            head = head.next;
            k--;
        }
        return head;
    }
    // 方法: 获取链表长度
    private int size(ListNode head){
        int count = 0;
        while(head != null){
            count++;
            head = head.next;
        }
        return count;
    }

//    删除链表中重复的节点
//    例如输入{1,2,3,3,4,4,5}时，对应的输出为 {1,2,5}
    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null) {
            return null;
        }

        ListNode dummy = new ListNode(-1); // 新链表的虚拟头节点
        ListNode newTail = dummy;  // 新链表的尾部，用于添加新节点
        ListNode cur = pHead;

        while (cur != null) {
            boolean isDuplicate = false;
            // 检查当前节点是否有重复
            while (cur.next != null && cur.val == cur.next.val) {
                isDuplicate = true;
                cur = cur.next;
            }

            // 如果当前节点不是重复节点，复制到新链表
            if (!isDuplicate) {
                newTail.next = new ListNode(cur.val); // 创建新节点并添加到新链表
                newTail = newTail.next;
            }
            // 移动到下一个节点
            cur = cur.next;
        }

        return dummy.next; // 返回新链表的头节点
    }

//    指定位置翻转
    public ListNode reverseBetween (ListNode head, int m, int n) {
        //  使用虚拟节点 处理头节点的情况
        ListNode dummy = new ListNode(-1);
        ListNode pre = dummy;
        ListNode cur = head;
        dummy.next = head;
//        找到m位置
        for (int i = 0; i < m; i++) {
            pre = cur;
            cur = cur.next;
        }
        return null;
    }
//    牛客 ONT10 牛群分割(类似于链表分割)
    public ListNode cow_partition(ListNode head, int x) {
        if (head == null) {
            return null;
        }

        // 定义两个虚拟节点 用于区分两个链表
        ListNode bigDummy = new ListNode(-1);
        ListNode smallDummy = new ListNode(-1);

        // 定义两个节点
        ListNode p1 = smallDummy;
        ListNode p2 = bigDummy;
        ListNode cur = head;

        // 开始遍历 将两个链表填充
        while (cur != null) {
            if (cur.val < x) {
                p1.next = cur;
                p1 = p1.next;
            } else {
                p2.next = cur;
                p2 = p2.next;
            }
            cur = cur.next;
        }

        // 避免形成环
        p2.next = null;

        // 合并两个链表
        p1.next = bigDummy.next;

        return smallDummy.next;
    }

    //        一个递增链表 将重复元素删除
    public ListNode removeDuplicates (ListNode head) {
//        链表为空或只有一个节点
        if (head == null || head.next == null){
            return null;
        }
        ListNode cur = head;
        while(cur != null && cur.next != null){
            if (cur.val == cur.next.val){
                cur.next = cur.next.next;
            }else{
                cur = cur.next;
            }
        }
        return head;
    }


    public int gcdInCycle(ListNode head) {
        if (head == null || head.next == null) {
            return -1; // 如果链表为空或只有一个节点，直接返回-1
        }

        // 使用快慢指针判断是否成环
        ListNode fast = head;
        ListNode slow = head;
        ListNode p1 = null;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                p1 = slow;
                break;
            }
        }

        if (p1 == null) {
            return -1; // 没有环
        }

        // 找到环的入口点
        ListNode start = head;
        while (start != p1) {
            start = start.next;
            p1 = p1.next;
        }

        // 遍历环并计算GCD
        ListNode nodeInCycle = start;
        int gcd = nodeInCycle.val;
        nodeInCycle = nodeInCycle.next;
        while (nodeInCycle != start) {
            gcd = gcd(gcd, nodeInCycle.val);
            nodeInCycle = nodeInCycle.next;
        }

        return gcd;
    }

    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
    public ListNode reverseBetween1(ListNode head, int m, int n) {
        if (head == null || m == n) {
            return head;
        }

        ListNode dummy = new ListNode(-1); // 虚拟节点
        dummy.next = head;
        ListNode pre = dummy;

        // 1. 找到反转区间的前一个节点
        for (int i = 1; i < m; i++) {
            pre = pre.next;
        }

        // 2. 开始反转区间 [m, n]
        ListNode cur = pre.next;
        ListNode start = cur;
        ListNode then = cur.next;

        for (int i = 0; i < n - m; i++) {
            cur.next = then.next;   // 断开 cur 和 then 的连接
            then.next = pre.next;   // 将 then 插入到 pre 后面
            pre.next = then;        // 更新 pre 的连接
            then = cur.next;        // 更新 then 为下一个节点
        }

        return dummy.next;
    }

}

